class Graph<T> {
    vertex: T[] = []
    edge: Map<T, T[]> = new Map()

    // 打印图
    print() {
        for (let i = 0; i < this.vertex.length; i++) {
            const v = this.vertex[i]
            const edges = this.edge.get(v)
            console.log(v, '->', edges?.join(' '));
        }
    }
    // 插入顶点
    addVertex(v: T) {
        this.vertex.push(v)
        this.edge.set(v, [])
    }
    // 插入边
    addEdge(v: T, u: T) {
        this.edge.get(v)?.push(u)
        this.edge.get(u)?.push(v)
    }
    // 广度优先遍历
    bfs() {
        // 无数据
        if (this.vertex.length === 0) return;

        // 只有一个顶点
        if (this.vertex.length === 1) {
            return this.vertex[0]
        }

        const visited = new Set<T>()
        for (let i = 0; i < this.vertex.length; i++) {
            const v = this.vertex[i]
            const edge = this.edge.get(v)
            if (!visited.has(v)) {
                console.log(v);
                visited.add(v)
            }



            if (!edge) continue;
            for (let j = 0; j < edge.length; j++) {
                if (visited.has(edge[j])) continue;
                visited.add(edge[j])
                console.log(edge[j]);
            }
        }
    }
    // 深度优先遍历
    dfs() {
        // 无数据
        if (this.vertex.length === 0) return;

        // 只有一个顶点
        if (this.vertex.length === 1) {
            return this.vertex[0]
        }

        const stack: T[] = [];
        const visited = new Set<T>();
        const v = this.vertex[0]
        stack.push(v)
        while (stack.length) {
            const stackTop = stack.pop()!
            const stackTopEdges = this.edge.get(stackTop)
            console.log(stackTop);
            visited.add(stackTop)
            if (!stackTopEdges) continue;
            for (let j = stackTopEdges.length - 1; j >= 0; j--) {
                if (visited.has(stackTopEdges[j])) continue;
                stack.push(stackTopEdges[j])
            }

        }

    }
}

const graph = new Graph<string>()

graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');
graph.addVertex('G');
graph.addVertex('H');
graph.addVertex('I');

graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');
graph.print()
console.log('.........');
// graph.bfs()
graph.dfs()


